#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 物品重量为整数 */
#define infinity (1e9)
typedef struct ObjNode *Objects;
struct ObjNode {
    ElemSet w; /* 重量 */
    int v; /* 价值 */
};

ElemSet **Create2DArray(int row, int col) {
    /* 动态声明row行col列的二维数组 */
    ElemSet *a, **t;
    int i;

    a = (ElemSet *)malloc(sizeof(ElemSet) * row * col);
    t = (ElemSet **)malloc(sizeof(ElemSet *) * row);
    for (i = 0; i < row; i++)
        t[i] = &a[col * i];
    return t;
}

void Free2DArray(ElemSet **t) {
    /* 释放二维数组空间 */
    free(t[0]);
    free(t);
}

ElemSet Knapsack01(int W, Objects s, int *opt, int n) {
    ElemSet **f, **x, ret;
    int V, i, v, pre_w;

    V = 0;
    for (i = 0; i < n; i++) {
        V += s[i].v;
    }
    f = Create2DArray(n, V +
                      1); /* f[i][v]存储前i个物品中选取总价值至少为v的物品，所需要的最小重量 */
    x = Create2DArray(n, V +
                      1); /* x[i][v]存储s[1]~s[i]对应总价值至少为v的子问题的最优选择 */
    for (i = 0; i < n; i++) {
        f[i][0] = 0; /* 价值为0时重量为0 */
        x[i][0] = 0;
    }
    for (v = 1; v <= V; v++) { /* 初始化f[0][v] */
        if (s[0].v < v) { /* 物品价值达不到当前价值，舍弃 */
            f[0][v] = infinity;
            x[0][v] = 0;
        } else { /* 物品价值至少达到当前价值，收入 */
            f[0][v] = s[0].w;
            x[0][v] = 1;
        }
    }
    for (i = 1; i < n; i++) {
        for (v = 1; v <= V; v++) {
            pre_w = (v < s[i].v) ? 0 : f[i - 1][v - s[i].v];
            if (s[i].w + pre_w < f[i - 1][v]) { /* 收入 */
                f[i][v] = s[i].w + pre_w;
                x[i][v] = 1;
            } else { /* 舍弃*/
                f[i][v] = f[i - 1][v];
                x[i][v] = 0;
            }
        }
    }
    for (v = V; v > 0; v--) {
        if (f[n - 1][v] <= W) {
            break; /* 找到重量在承重范围内的最大的v */
        }
    }
    ret = v;
    opt[n - 1] = x[n - 1][v]; /* 最后一个物品的最优选择 */
    for (i = n - 2; i >= 0; i--) { /* 获得剩余物品的最优解 */
        if (opt[i + 1] == 1) { /* 如果后一个物品被放入背包 */
            opt[i] = x[i][v - s[i +
                                1].v]; /* 则前一个物品对应价值为v-s[i+1].v时的最优解 */
            v -= s[i + 1].v; /* 更新当前最优价值 */
        } else { /* 如果后一个物品被舍弃 */
            opt[i] = x[i][v]; /* 则前一个物品对应价值不变的最优解 */
        }
    }
    Free2DArray(f);
    Free2DArray(x);

    return ret;
}

int FindMaxValue(Objects s, int n) {
    int v_max, i;

    v_max = -1;
    for (i = 0; i < n; i++) {
        if (s[i].v > v_max) {
            v_max = s[i].v;
        }
    }
    return v_max;
}

/* 算法16-3：基于动态规划的离散背包问题近似算法 KnapsackDPApproximation(W,s,x,n,eps) */
ElemSet KnapsackDPApproximation(ElemSet W, Objects s, int *x, int n,
                                double eps) {
    int v_max, i, sum;
    double theta;
    Objects sp;

    v_max = FindMaxValue(s, n);
    theta = eps * v_max / (n + n); /* 设置缩放因子 */
    sp = (Objects)malloc(sizeof(struct ObjNode) * n);
    for (i = 0; i < n; i++) {
        sp[i].v = (int)((double)s[i].v / theta); /* 将物品价值进行缩放 */
        sp[i].w = s[i].w;
    }
    Knapsack01(W, sp, x,
               n); /* 求解缩放后的离散背包问题，得到最优解x */
    sum = 0;
    for (i = 0; i < n; i++) { /* 计算近似最优总价值 */
        sum += (s[i].v * x[i]);
    }
    return sum;
}
/* 算法16-3 结束 */

int main(void) {
    Objects s;
    int W;
    int *opt;
    double eps;
    int n, i;

    scanf("%d %d %lf", &n, &W, &eps);
    s = (Objects)malloc(sizeof(struct ObjNode) * n);
    opt = (int *)malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &s[i].w);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &s[i].v);
    }
    printf("%d\n", Knapsack01(W, s, opt, n));
    for (i = 0; i < n; i++) {
        printf("%d ", opt[i]);
    }
    printf("\n%d\n", KnapsackDPApproximation(W, s, opt, n, eps));
    for (i = 0; i < n; i++) {
        printf("%d ", opt[i]);
    }
    return 0;
}